
import random


class Solution:

    def findKthLargest(self, nums: list[int], k:int) -> int:
        # 方法一
        # 从小到大排序
        # return sorted(nums)[len(nums) - k]

        # 方法二
        # 快速选择
        def quick_select(nums, k):

            pivot = random.choice(nums)
            big, equal, small = [], [], []

            for num in nums:
                if num > pivot:
                    big.append(num)
                elif num == pivot:
                    equal.append(num)
                else:
                    small.append(num)

            if k <= len(big):
                return quick_select(big, k)
            
            if len(nums) - len(small) < k:
                return quick_select(small, k - len(nums) + len(small))
            
            return pivot
        
        return quick_select(nums, k)
        

if __name__ == "__main__":

    nums = [3,2,1,5,6,4]
    # print(nums)
    k = 2
    sol = Solution()
    res = sol.findKthLargest(nums, k)
    print(res)
    


